这是昨天做的一套比赛，2014年的一场北美地区赛，就不把题目挂上来了，直接放题意和代码吧。
题目网址在此
##A·Height Ordering
一眼题，求一串数列冒泡排序时进行操作的次数。比赛的时候是队友做出来的，只要懂如何写冒泡排序即可，复杂度为O(N^2)。
#include<iostream>
#include<algorithm>
using namespace std;
int main(){
int t;
cin >> t;
while(t--)
{
int cnt,a[20],sum = 0;
cin >> cnt;
for(int i = 0;i < 20;i++)
cin >> a[i];
for(int i = 0;i < 20;i++)
{
for(int j = i;j < 20;j++)
{
if(a[i] > a[j])
{
sum++;
swap(a[i],a[j]);
}
}
}
cout << cnt << " " << sum << endl;
}
return 0;
}
##B·Islands in the Data Stream
一眼题，当时这道题目是我做的，队友表示看不懂这道题目的意思，我根据他的样例脑补了一下规律。就是每次删除一串数列中最小的一个数，求剩余的子串数，需要注意的是可能会有重复计算，如 0,1,0,0,2,0，如果不排除重复计算的结果，答案则为3，所以这里用set进行处理，最后输出set的size即可。
#include<iostream>
#include<set>
#include<map>
#include<algorithm>
using namespace std;
int main(){
int t;
cin >> t;
while(t--)
{
int cnt,a[12];
set<int>st;
set<pair<int,int> > mp;
cin >> cnt;
for(int i = 0;i < 12;i++)
{
cin >> a[i];
st.insert(a[i]);
}
set<int>::iterator it = st.begin();
int siz = st.size();
while(siz--)
{
for(int i = 0;i < 12;i++)
{
if(a[i] == *it)
a[i] = -1;
}
int ok = 0,flag = 0;
for(int i = 0;i < 12;i++)
{
if(ok)
{
if(a[i] != -1)
{
continue;
}
else
{
ok = 0;
mp.insert(make_pair(flag,i - 1));
}
}
else
{
if(a[i] != -1)
{
ok = 1;
flag = i;
}
else
{
continue;
}
}
}
it++;
}
cout << cnt << " " << mp.size() << endl;
}
return 0;
}
##C·Floating-Point Format Conversion
听浙大的大神们说是什么一道浮点精度的模拟题（？）有很多判断的条件，ORZZ暂时没看懂，留坑待填
##D·Happy Happy Prime Prime
一眼题，给出一个数先判断这个数是不是素数，如果是素数，判断其经过一定的运算之后能否成为1，运算为对数上每一位的数进行平方求和，注意加上vis判断，防止死循环。
#include<iostream>
#include<cstring>
#include<algorithm>
using namespace std;
bool isprime(int x)
{
if(x == 1 || x == 2)
return false;
for(int i = 2;i * i <= x;i++)
{
if(x % i == 0)
return false;
}
return true;
}
int main(){
int t;
cin >> t;
while(t--)
{
int cnt,n,vis[1 << 16];
cin >> cnt >> n;
cout << cnt << " " << n;
if(!isprime(n))
{
cout << " NO\n";
}
else
{
memset(vis,0,sizeof(vis));
while(!vis[n] && n != 1)
{
int te = 0;
vis[n] = 1;
while(n)
{
te += (n % 10) * (n % 10);
n /= 10;
}
n = te;
}
if(n == 1)
cout << " YES\n";
else
cout << " NO\n";
}
}
return 0;
}
##E·Mancala
规律题，ORZ比赛的时候明明非常接近规律了可就是死活没推出来啊，赛后一经点拨就恍然大悟
QAQ买不起专业版的MDPAD2，就不发图了，大意就是给出几个筒子，让你放几个小点进去，每次的操作是找到一个筒子满足b[n]=n，就将其中的小点全部分配给前面的筒子，直到最后所有的小点都在第一个筒子里面。规律就是每次都会把一个筒清空，那么就用递推就行了，从前一个的情况往后一个情况推，每次多出一个满的筒子，最后保存答案，离线回答一下就行了。
#include<iostream>
#include<vector>
#include<cstring>
#include<algorithm>
using namespace std;
int main(){
int mark[2000][80],siz[2000];
siz[0] = 1,mark[0][0] = 1;
for(int i = 1;i < 2000;i++)
{
for(int j = 0;j < siz[i - 1];j++)
{
mark[i][j] = mark[i - 1][j];
}
siz[i] = siz[i - 1];
int ok = 0,pos;
for(int j = 0;j < siz[i];j++)
{
if(mark[i][j] == 0)
{
ok = 1;
pos = j;
break;
}
}
if(ok)
{
for(int j = 0;j < pos;j++)
{
mark[i][j]--;
}
mark[i][pos] = pos + 1;
}
else
{
for(int j = 0;j < siz[i];j++)
{
mark[i][j]--;
}
siz[i]++;
mark[i][siz[i] - 1] = siz[i];
}
}
int t;
cin >> t;
while(t--)
{
int cnt,n;
cin >> cnt >> n;
cout << cnt << " " << siz[n - 1] << endl;
for(int i = 0;i < siz[n - 1];i++)
{
if(i % 10 == 0)
cout << mark[n - 1][i];
else
cout << " " << mark[n - 1][i];
if((i + 1) % 10 == 0 || i == siz[n - 1] - 1)
cout << endl;
}
}
return 0;
}
##F·A Rational Sequence
队友做出来的，题意就是构造一棵树，满足三个条件：
The label of the root is 1/1
The left child of label p/q is p/(p + q)
The right child of label p/q is (p + q)/q
给你一个节点，让你求下一个节点是多少。
当时是队友做出来的，暂不明，待填
##G·Growing Rectangular Spiral
这道题是我做的，题意是一个点由原点出发，依照右上左下的次序运动，每次运动出来的直线至少比前一条长1，现在给你一个坐标，让你判断这个点能否到达这个坐标，输出使到达这个坐标最短的路径的方法。当时我做出了一个假设，如果能到达的话，最多只需要6次，然后要先判断这个坐标的横坐标是不是小于纵坐标，如果成立就做两次，否则判断能不能做6次到，六条线的长度分别为1,2,3,x+5-y,x+2,x+3。代码就不放了，最简单的if判断而已
##F·Farey Sums
找规律题，给你一个n，找出所有的a/b满足(0 < a <= b)且a与b互质，将其升序排序，然后求b[i]的分母/b[i+1]的分母的和，规律是每加入一对互质的数，就会让最终答案+3，搞一搞就出来了。然而我并没有在比赛的时候发现这个规律……果然含是我的脑洞不够大的缘故吗。8-20ps：代码是写出来的结果交上去T了，然后我又离线搞了一下，才1w的数组竟然不让提交我也醉了，估计把代码扔着吧。
#include<iostream>
#include<cstring>
#include<algorithm>
#include<cstdio>
using namespace std;
int gcd(int x,int y)
{
return (y == 0 ? x : gcd(y,x % y));
}
int main(){
//freopen("h.in","r",stdin);
//freopen("h.txt","w",stdout);
int mark[10005];
mark[2] = 4;
for(int i = 3;i <= 10000;i++)
{
mark[i] = mark[i - 1];
for(int j = 1;j < i;j++)
{
if(gcd(i,j) == 1)
mark[i] += 3;
}
}
int t;
cin >> t;
while(t--)
{
int cnt,n;
cin >> cnt >> n;
cout << cnt << " " << mark[n] + 1 << "/2\n";
}
return 0;
}
##I·The Queen’s Super-circular Patio
迷之数学，并不能懂……